package apii.algorithm.fingerprints;

import java.awt.List;
import java.math.*;
import java.util.*;

/**
 * <b>Note:</b> thread safe.
 * <p>
 * <b> Note:</b> Doesn't create threads.
 * <p>
 * For key to what is this see <a href=
 * "http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BD%D0%B5%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D0%B5%D0%BA%D0%B0%D1%8E%D1%89%D0%B8%D1%85%D1%81%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2"
 * >wiki</a> or <a href="http://e-maxx.ru/algo/dsu">e-maxx</a>
 * 
 * @author Alex
 * 
 * @param <T>
 */
public class Sets<T> {
	private Random rnd = new Random();
	private Map<T, T> m = new HashMap<T, T>();

	public T getId(T t) {
		if (t == null)
			throw new IllegalArgumentException();
		return getIdNotExists(t);
	}

	public T union(T t1, T t2) {
		return unionHeads(getIdNotExists(t1), getIdNotExists(t2));
	}

	private T unionHeads(T t1, T t2) {
		if (rnd.nextBoolean()) {
			m.put(t1, t2);
			return t2;
		}
		m.put(t2, t1);
		return t1;
	}

	private T getIdNotExists(T t) {
		T h = m.get(t);
		if (h == null) {
			m.put(t, t);
			return t;
		}
		if (t.equals(h))
			return t;
		return getIdExists(h);
	}

	private T getIdExists(T t) {
		T h = m.get(t);
		return t.equals(h) ? t : getIdExists(h);
	}
}
